Find smallest letter greater than target¶
Time: O(LogN); Space: O(1); easy
Given a list of sorted characters letters containing only lowercase letters, and given a target letter target, find the smallest element in the list that is larger than the given target.
Letters also wrap around.
For example, if the target is target = ‘z’ and letters = [‘a’, ‘b’], the answer is ‘a’.
Example 1:
Input: letters = [“c”, “f”, “j”], target = “a”
Output: “c”
Example 2:
Input: letters = [“c”, “f”, “j”], target = “c”
Output: “f”
Example 3:
Input: letters = [“c”, “f”, “j”], target = “d”
Output: “f”
Example 4:
Input: letters = [“c”, “f”, “j”], target = “g”
Output: “j”
Example 5:
Input: letters = [“c”, “f”, “j”], target = “j”
Output: “c”
Example 6:
Input: letters = [“c”, “f”, “j”], target = “k”
Output: “c”
Constraints:
letters has a length in range [2, 10000].
letters consists of lowercase letters, and contains at least 2 unique letters.
target is a lowercase letter.
Hints:
Try to find whether each of 26 next letters are in the given string array.
1. Binary Search [O(LogN), O(1)]¶
[1]:
import bisect
class Solution1(object):
"""
Time: O(LogN)
Space: O(1)
"""
def nextGreatestLetter(self, letters, target):
"""
:type letters: List[str]
:type target: str
:rtype: str
"""
i = bisect.bisect_right(letters, target)
return letters[0] if i == len(letters) else letters[i]
[2]:
s = Solution1()
letters = ["c", "f", "j"]
target = "a"
assert s.nextGreatestLetter(letters, target) == "c"
letters = ["c", "f", "j"]
target = "c"
assert s.nextGreatestLetter(letters, target) == "f"
letters = ["c", "f", "j"]
target = "d"
assert s.nextGreatestLetter(letters, target) == "f"
letters = ["c", "f", "j"]
target = "g"
assert s.nextGreatestLetter(letters, target) == "j"
letters = ["c", "f", "j"]
target = "j"
assert s.nextGreatestLetter(letters, target) == "c"
letters = ["c", "f", "j"]
target = "k"
assert s.nextGreatestLetter(letters, target) == "c"